package binary_tree

import "container/list"

func IsCBT(node *Node) bool {
	if node == nil {return false}
	queue := list.New()
	queue.PushBack(node)
	for queue.Len() > 0 {
		node = queue.Remove(queue.Front()).(*Node)
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}

		if node.Left == nil && node.Right != nil {
			return false
		}
		// 情况三出现则证明队列里的都是叶子节点
		if (node.Left != nil && node.Right == nil) || (node.Left == nil || node.Right == nil){
			if node.Left != nil && node.Right == nil {
				queue.PushBack(node.Left)
			}
			for queue.Len() > 0 {
				node = queue.Remove(queue.Front()).(*Node)
				if node.Left != nil || node.Right != nil{
					// 不是叶子节点直接返回
					return false
				}
			}
		}
	}
	return true
}


type CBTInfo struct {
	IsCBT bool
	IsFull bool
	Height int
}

func IsCBT2 (node *Node) bool {
	if node == nil {return false}
	return process(node).IsCBT
}

func process(node *Node) CBTInfo {
	if node == nil {
		return CBTInfo{true, true, 0}
	}
	leftInfo := process(node.Left)
	rightInfo := process(node.Right)
	isCBT, isFull := false, false
	var height int

	isFull = leftInfo.IsFull && rightInfo.IsFull && leftInfo.Height == rightInfo.Height
	height = max(leftInfo.Height, rightInfo.Height) + 1
	if isFull {
		isCBT = true
	} else {
		if leftInfo.IsCBT && rightInfo.IsFull && leftInfo.Height == rightInfo.Height+1 {
			isCBT = true
		}
		if leftInfo.IsFull && rightInfo.IsCBT && leftInfo.Height == rightInfo.Height {
			isCBT = true
		}
		if leftInfo.IsFull && rightInfo.IsFull && (leftInfo.Height == rightInfo.Height+1 || leftInfo.Height == rightInfo.Height) {
			isCBT = true
		}
	}


	return CBTInfo{isCBT, isFull, height}
}